#include <iostream>
#include "time.h"

using namespace std;

void quicksort(int *arr,int left,int right){
    srand(time(NULL));
    if(left>=right) return;
    int l=left,r=right,pivot_key=left+rand()%(right-left),pivot=arr[pivot_key],tmp=0;//left+rand()%(right-left)
    tmp=arr[right];
    arr[right]=arr[pivot_key];
    arr[pivot_key]=tmp;
    --r;
    while(l<r){
        while(l<r && arr[l] < pivot) ++l;
        while(l<r && arr[r] > pivot) --r;
        if(arr[l] > arr[r]){
            tmp = arr[r];
            arr[r] = arr[l];
            arr[l] = tmp;
        }
        ++l;--r;
    }
    if(r<0) ++r;
    if(l>right) --l;
    while(arr[r] < pivot) ++r;
    cout << l << " " << r << endl;
    if(arr[r] > pivot)
    {
        tmp=arr[right];
        arr[right]=arr[r];
        arr[r]=tmp;
    }
    quicksort(arr,left,r-1);
    quicksort(arr,r+1,right);
}

int main(int argc, char const *argv[])
{
    int test[10]={7,3,9,1,0,66,2,33,40,99};
    quicksort(test,0,9);
    for(int i=0;i<10;i++){
        cout << test[i] << " ";
    }
    cout << endl;
    return 0;
}
